#include "string_array.h"

using namespace std;
//字符串初始化
myStr::myStr(const char* s) {
    if (s == NULL) {
        this->data = NULL;
        this->length = 0;
        this->next = NULL;
        this->nextVal = NULL;
    }
    else {
        int i = 0;
        while (s[i] != '\0')
            i++;
        this->data = new char[i + 1];
        for (int j = 0; j < i; j++)
            this->data[j] = s[j];
        this->data[i] = '\0';
        this->length = i;
        this->next = new int[i];
        this->nextVal = new int[i];
        this->kmp_next();
        this->kmp_nextVal();
    }
}

//字符串销毁
myStr::~myStr() {
    if (this->data != NULL)
        delete[] data;
    if (this->next != NULL)
        delete[] next;
    if (this->nextVal != NULL)
        delete[] nextVal;
}

//kmp辅助数组
void myStr::kmp_next() {
    next[0] = 0, next[1] = 1;
    int i = 1, j = 0;
    while (i < this->length-1) {
        if (this->data[i] == this->data[j]) {
            i++, j++;
            next[i] = j+1;
        }
        else if (this->data[i] != this->data[j] && j == 0) {
            i++;
            next[i] = j+1;
        }
        else
            j = next[j]-1;
    }
}

void myStr::kmp_nextVal() {
    nextVal[0] = 0, nextVal[1] = 1;
    int i = 1, j = 0;
    while (i < this->length - 1) {
        if (this->data[i] == this->data[j]) {
            i++, j++;
            nextVal[i] = j+1;
        }
        else if (this->data[i] != this->data[j] && j == 0) {
            i++;
            nextVal[i] = j + 1;
        }
        else
            j = nextVal[j]-1;
    }
    for (int k = 1; k < this->length; k++) {
        if (this->data[k] == this->data[nextVal[k] - 1])
            nextVal[k] = nextVal[nextVal[k] - 1];
    }
}

//串的替换
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int i = start - 1, j = 0, z = 0, z1 = -1, k = 0;
    while (i < S.length) {
        if (j == T.length ) {
            break;
        }
        if (S.data[i] == T.data[j]) {
            i++, j++;
        }
        else {
            i++, j = 0;
        }
    }
    if (!j)
        return false;
    else {
        S.length = S.length - T.length + V.length;
        char* temp = new char[S.length + 1];
        char* f = S.data;
        while(k < i - j) {
            temp[k] = S.data[z];
            z++, k++;
        }
        for (k; k < i - j + V.length; k++) {
            z1++;
            temp[k] = V.data[z1];
        }
        for (k; k < S.length; k++) {
            temp[k] = S.data[i];
            i++;
        }
        temp[S.length] = '\0';
        S.data = temp;
        delete[] f;
        S.kmp_next();
        S.kmp_nextVal();
        return true;
    }

}

//字符串匹配
int kmpMatch(const myStr& S, const myStr& T) {
    int i = 0, j = 0;
    while (j < T.length&&i<S.length) {
        if (S.data[i] == T.data[j]) {
            i++, j++;
        }
        else {
            if (j == 0)
                i++;
            else if (T.nextVal[j] == 0)
                j = T.nextVal[j];
            else
                j = T.nextVal[j]-1;
        }
    }
    if (j == T.length) {
        return i - j + 1;
    }
    else
        return -1;
}

//简单字符串匹配
int simpleMatch(const myStr& S, const myStr& T) {
    int i=0, j = 0;
    int d = 0;
    while (i < S.length && j < T.length) {
        if (S.data[i] == T.data[j]) {
            i++, j++;
        }
        else {
            j = 0, d++;
            i = d;
        }
    }
    if (j == T.length)
        return i - j + 1;
    else
        return -1;
}

void myStr::print() {
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext() {
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal() {
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

//初始化稀疏矩阵
myMatrix::myMatrix() { 
    this->rowNum = 0;
    this->colNum = 0;
    this->nodeNum = 0;
    this->nodeList = NULL;
};
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* t) {
    this->rowNum = rNum;
    this->colNum = cNum;
    this->nodeNum = nNum;
    this->nodeList = new matrixNode[this->nodeNum];
    int j = 0;
    int* num = new int[cNum];
    int* cpot = new int[cNum];
    for (int i = 0; i < cNum; i++) {
        num[i] = 0;
    }
    for (int i = 0; i < nNum; i++) {
        ++num[t[i * 3 + 1]];
    }
    cpot[0] = 0;
    for (int i = 1; i < cNum; i++) {
        cpot[i] = cpot[i - 1] + num[i - 1];
    }
    for (int i = 0; i < nNum; i++) {
        this->nodeList[i].row = t[j];
        j++;
        this->nodeList[i].col = t[j];
        j++;
        this->nodeList[i].value = t[j];
        j++;
    }
    for (int k = 0; k < nNum-1; k++) {
        for (int z = 0 ; z <nNum-1; z++) {
            if (this->nodeList[z].row > this->nodeList[z + 1].row) {
                int temp1 = this->nodeList[z].row;
                this->nodeList[z].row = this->nodeList[z + 1].row;
                this->nodeList[z + 1].row =temp1;
                int temp2 = this->nodeList[z].col;
                this->nodeList[z].col = this->nodeList[z + 1].col;
                this->nodeList[z + 1].col = temp2;
                int temp3 = this->nodeList[z].value;
                this->nodeList[z].value = this->nodeList[z + 1].value;
                this->nodeList[z + 1].value = temp3;
           }
        }
    }
    
    for (int k = 0; k < nNum - 1; k++) {
        for (int z = 0; z < nNum - 1; z++) {
            if (this->nodeList[z].row == this->nodeList[z + 1].row&&this->nodeList[z].col > this->nodeList[z + 1].col) {
                int temp1 = this->nodeList[z].row;
                this->nodeList[z].row = this->nodeList[z + 1].row;
                this->nodeList[z + 1].row = temp1;
                int temp2 = this->nodeList[z].col;
                this->nodeList[z].col = this->nodeList[z + 1].col;
                this->nodeList[z + 1].col = temp2;
                int temp3 = this->nodeList[z].value;
                this->nodeList[z].value = this->nodeList[z + 1].value;
                this->nodeList[z + 1].value = temp3;
            }
        }
    }
    
}

//实现快速转置算法
void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = this->colNum;
    T.colNum = this->rowNum;
    T.nodeNum = this->nodeNum;
    T.nodeList = new matrixNode[T.nodeNum];
    //构建需要转置的矩阵的辅助数组
    int* num = new int[this->colNum];
    int* cpot = new int[this->colNum];
    for (int i = 0; i < this->colNum; i++) {
        num[i] = 0;
    }
    for (int i = 0; i < this->nodeNum; i++) {
        ++num[this->nodeList[i].col];
    }
    cpot[0] = 0;
    for (int i = 1; i < this->colNum; i++) {
        cpot[i] = cpot[i - 1] + num[i - 1];
    }
    if (T.nodeNum) {
        for (int y = 0; y < T.nodeNum; y++) {
            int col = this->nodeList[y].col;
            int T_nodeList = cpot[col];
            T.nodeList[T_nodeList].row = this->nodeList[y].col;
            T.nodeList[T_nodeList].col = this->nodeList[y].row;
            T.nodeList[T_nodeList].value = this->nodeList[y].value;
            ++cpot[col];
        }
    }
}

myMatrix::~myMatrix() {
    this->rowNum = 0;
    this->colNum = 0;
    this->nodeNum = 0;
    delete[] this->nodeList;
}

void myMatrix::printMatrix() {
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
